package com.squirrel.michale;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/3/13 8:15 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode2439_2 {

    public int minimizeArrayValue(int[] nums) {
        int left = 0, right = 1000000000;
        while (left < right) {
            int mid = left + ((right - left) >>1);
            if (check(nums, mid)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return left;
    }

    boolean check(int[] nums, int k) {
        long have = 0;
        for (int n : nums) {
            if (n <= k) {
                have += k - n;
            } else {
                if (have < n - k) {
                    return false;
                } else {
                    have -= (n - k);
                }
            }
        }
        return true;
    }
}
